package cn.leonis.algorithm.c1.p1;

import cn.leonis.algorithm.lib.In;
import cn.leonis.algorithm.lib.StdIn;
import cn.leonis.algorithm.lib.StdOut;

import java.util.Arrays;

/**
 * @author Tobi
 * @time 2021-06-03 3:50 PM
 * 实现二分查找
 */
public class BinarySearch {

    private BinarySearch() {

    }

    public static int indexOf(int[] a, int key) {
        // a是排好序的数组
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid]) {
                hi = mid - 1;
            }else if (key > a[mid]) {
                lo = mid + 1;
            }else {
                return mid;
            }
        }

        return -1;
    }

    @Deprecated
    public static int rank(int key, int[] a) {
        return indexOf(a, key);
    }

    public static void main(String[] args) {
        // 读取白名单
        // In in = new In(args[0]);
        In in = new In("C:\\Workspace\\Java\\interview\\src\\main\\java\\cn\\leonis\\algorithm\\c1\\p1\\largeAllowlist.txt");
        int[] whiteList = in.readAllInts();

        Arrays.sort(whiteList);

        In in1 = new In("C:\\Workspace\\Java\\interview\\src\\main\\java\\cn\\leonis\\algorithm\\c1\\p1\\largeText.txt");
        int[] allList = in1.readAllInts();

/*        while (!StdIn.isEmpty()) {
            int key = StdIn.readInt();
            if (BinarySearch.indexOf(whiteList, key) == -1) {
                StdOut.println(key);
            }
        }*/

        for (int i = 0; i < allList.length; i++) {
            if (BinarySearch.indexOf(whiteList, allList[i]) == -1) {
                StdOut.println(allList[i]);
            }
        }

    }
}
